1. Field of the Invention
The present invention relates to an associative memory device, having a plurality of words for storing data, for detecting the coincidence/non-coincidence between the data stored in the respective words and input search data in the plurality of words.
2. Description of the Related Art
A circuit block diagram showing an associative memory device having the search function described above is shown in FIG. 3.
This associative memory device 100 comprises a large number of memory words 110, 120, . . . , constituted by a plurality of associative memory cells. The associative memory device 100 also comprises a search register 160 in which search data are stored. The bit pattern of all or predetermined part of the search data stored in the search register are compared with the bit pattern of a corresponding part of data stored in the memory words to check the coincidence/non-coincidence therebetween. Coincidence/non-coincidence signals are output to coincidence lines 111, 121, . . . , arranged for the respective memory words.
The signal of the coincidence line is input to a priority encoder 170. The priority encoder outputs an address signal 171 corresponding to a memory word, having the highest priority, of the memory words to which the coincidence signals are output.
Since such an associative memory device has a price per bit which is higher than a conventional memory device, maintenance for word data is necessarily performed. More specifically, data to be searched are not stored in all the memory words constituting the associative memory device, and some memory words do not have valid data stored therein and are set in an empty state. New valid data may be written in the memory words set in the empty state. In this case, it is very complicated that memory words set in the empty state are managed by an external device.
As an associative memory device to solve the above problem, as disclosed in Japanese Examined Patent Publication No. 61-31558, an associative memory device having the following arrangement is known. Storage circuits (empty bits) for storing whether words are allowed to write information therein are arranged for the respective words, so that the information can be written in the words allowed to write information therein in the device without address management by an external device.
As disclosed in Japanese Unexamined Patent Publication No. 2-18790, an associative memory device which can control whether a word is to be searched by an empty bit (whether a coincidence output is made or not) is known.
In the associative memory device, when unnecessary word data left a predetermined period of time after registration or a coincidence output is made, the empty bit of the word to be erased is reset. For this purpose, a specific word must be selected by address designation. Although the later associative memory device has a simultaneous reset function for empty bits, the associative memory device does not have a function of simultaneously resetting only a plurality of specific words.
Associative memory devices which are proposed by the present applicant in Japanese Unexamined Patent Publication Nos. 7-105689, 8-106788, and 8-124386 will be described below with reference to FIG. 4. Each of these applications proposes an associative memory device having an empty flag register 220 for storing whether a word is allowed to write information therein, a hit hysteresis flag register 230 for storing whether a word is a word in which coincidence is detected at least once in previous searching operations, and a storage state change circuit 240 in which flags stored in the empty flag register 220 are changed from a valid state to an invalid state depending on the hit hysteresis at once, or for respective words, or for respective sets of words.
In the associative memory device having conventional empty bits, in order to reset the empty bit of a specific word, a corresponding word must be selected by address designation. In addition, when there are a plurality of corresponding words, selecting and erasing operations by address designation must be repeated. For this reason, the associative memory device has problems that complex control must be performed for address designation and that a high-speed operation cannot be easily achieved.
Since an empty bit and a circuit for controlling the empty bit are required for each word, it is important for obtaining a high integration density to decrease the number of elements for realizing these functions. However, a prior art concerning this technique is not actually disclosed.
Furthermore, in the associative memory device proposed by the present applicant, as a means for realizing empty flags and hit hysteresis flags is constituted by a flip-flop having a set/reset function and some logic circuits. Since these circuits are required for each word, a circuit arrangement disadvantageously increases in size.
For a high-speed operation, a coincidence line output (251 in FIG. 4) is held, and bit lines and coincidence lines of the respective words must be initialized for a next searching operation during a priority encoder processing. For this reason, another hit flag must be arranged independently of the hit hysteresis flag, and the circuit further increases in size disadvantageously.
In a general associative memory device has a mechanism which receives a coincidence line output or a signal of a hit flag holding the coincidence line output to cause a priority encoder to encode a hit address. In the conventional associative memory device, upon completion of the searching operation, a coincidence line output is reset for a next searching operation. Words having hit flags hold the hit flags until the next searching operation is performed. For this reason, when the coincidence states of valid words are checked after coincidence words are made invalid, a searching operation must be performed again. Of a series of operations in the associative memory device, the searching operation requires a processing time and current consumption. For this reason, a re-searching operation for only checking a coincidence state degrades the performance of the system. Therefore, when a word is made invalid, if the hit flag of the word can be reset (incoincidence state), a coincidence state after the word is made invalid can be checked by operating a priority encoder. A processing speed of the system can be increased, and current consumption of the system can be reduced.